/**
 *  \file list.h
 *
 *  \brief Double Linked List.
 *
 *  \author   Michael J. Hohmann  <michael.hohmann@linde-mh.de>
 *
 *  This header file provide a collection of macros to maintain linked lists.
 *
 *  A list consist of a head object and a an arbitrarily number of linked node objects.
 *  Each head has internaly linked two node objects as header and trailer of the linked list.
 *  An empty (and initialized) head looks like this.
 *
 *  \code
 *              Header      Trailer
 *   NULL<------[prev]<-----[prev]
 *              [next]----->[next]----->NULL
 *  \endcode
 *
 * A linked list with two elements looks like this.
 *   \code
 *              Header      1st         2nd         Trailer
 *   NULL<------[prev]<-----[prev]<-----[prev]<-----[prev]
 *              [next]----->[next]----->[next]----->[next]----->NULL
 *   \endcode
 *
 * Common use:
 * \code
 * LIST_NODE_STRUCT(node,int);
 * LIST_HEAD_STRUCT(head,struct node);
 *
 * struct node a,b,c;
 * struct head my_head;
 *
 * LIST_INITIALIZE(&my_head);
 *
 * LIST_DATA(&a)=1;
 * LIST_DATA(&b)=2;
 * LIST_DATA(&c)=3;
 *
 * LIST_PUSH_FRONT( &my_head, &a );
 * LIST_PUSH_BACK(  &my_head, &b );
 * LIST_PUSH_BACK(  &my_head, &c );
 *
 * LIST_FOR_EACH(&my_head, p)
 * {
 *   print("%i\n",*LIST_DATA(&p) );
 * }
 * \endcode
 *
 */

#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

#ifdef __cplusplus
   extern "C" {
#endif

/*================================================[ public includes  ]================================================*/
#include "../cfg/prj.h"

/*================================================[ public defines   ]================================================*/

/** Struct definition of list node.
 *
 *  The macro LIST_NODE_STRUCT() define a struct with the ability of being linked in a double
 *  linked list and provide the passed datatype as user data.
 *
 *  \param name         Name for the new type.
 *
 *  \param type         Type specifier of userdata.
 *
 *  \see LIST_HEAD_STRUCT()
 *
 *  \hideinitializer
 */
#define LIST_NODE_STRUCT(name,type)    struct name                \
                                       {                          \
                                          struct name *prev;      \
                                          struct name *next;      \
                                          type data;              \
                                       }

/** Stuct definition of list head.
 *
 *  LIST_HEAD_TYPEDEF() will create a list-head for passed type.
 *  The type of list nodes have to be declared as LIST_NODE_STRUCT() before.
 *
 *  \param name         Name of the created struct.
 *
 *  \param type         Type of user data.
 *
 *  \see LIST_NODE_STRUCT()
 *
 *  \hideinitializer
 */
#define LIST_HEAD_STRUCT(name,type)    struct name                \
                                       {                          \
                                          struct                  \
                                          {                       \
                                             type *prev;          \
                                             type *next;          \
                                          } header,   trailer;    \
                                       }

/** Initialization of list handle.
 *
 *  LIST_INIT() will initialize the passed list-head object.
 *  A call of LIST_INIT() is neccessary before the use of any other macro.
 *
 *  \param list          Handle to a list object.
 *
 *  \hideinitializer
 */
#define LIST_INIT( list )     do{                                                      \
                                 (list)->header.next   = (void*)&(list)->trailer;      \
                                 (list)->header.prev   = (void*) 0;                    \
                                 (list)->trailer.next  = (void*) 0;                    \
                                 (list)->trailer.prev  = (void*)&(list)->header;       \
                              }while(0)

/** Get pointer to user data
 *
 *  LIST_DATA() will return a pointer to the user data of a list element.
 *
 *  \param node         Handle to an list element.
 *
 *  \return             Pointer to the user data object of the list element.
 *
 *  \hideinitializer
 */
#define LIST_DATA( node )     ( & ((node)->data) )

/** Get next list element.
 *
 *  LIST_NEXT() will return a pointer to the next element associated to the lis.
 *
 *  \param node         Pointer to a existing list element, have to be associated to a list.
 *
 *  \return             Pointer to the next list object or NULL if node was the the last node of list.
 *
 *  \see LIST_PREV()  LIST_LAST()
 *
 *  \test Call with an node of a list with only one element. Result must be NULL.
 *  \test Call with the last node of a filled list.Result must be NULL.
 *  \test Call with the first node of a filled list.Result must be a pointer to the second node.
 *  \test Call with any node of a filled list.Result must be a pointer to the next node.
 *
 *  \hideinitializer
 */
#define LIST_NEXT(node)  ( (node)->next->next ? (node)->next : (void*) 0 )

/** Get previous list element.
 *
 *  LIST_PREV() will return a pointer to the previous object of the list. If no
 *  previous element exist NULL will be returned.
 *
 *  \param node      Pointer to a list element, have to be associated to a list.
 *
 *  \return          Pointer to the previous object or NULL if node was the first nod of list.
 *
 *  \see  LIST_NEXT() LIST_FIRST()
 *
 *  \test Call with an node of a list with only one element. Result must be NULL.
 *  \test Call with the first node of a filled list.Result must be NULL.
 *  \test Call with the last node of a filled list.Result must be a pointer to the previous node.
 *  \test Call with any node of a filled list.Result must be a pointer to the previous node.
 *
 *  \hideinitializer
 */
#define LIST_PREV(node)  ( (node)->prev->prev ? (node)->prev : (void*) 0 )

/** Retrieve pointer to first element of list.
 *
 *  LIST_FIRST() will return the first element of the list. If list is empty NULL will be returned.
 *
 *  \param list         Handle to an initialized linked list.
 *
 *  \return             Pointer to the first object in list or
 *                      NULL if list is empty.
 *
 *  \see  LIST_LAST() LIST_NEXT() LIST_PREV() LIST_POP() LIST_UNSHIFT()
 *
 *  \test Call with a list with only one node result must be NULL.
 *  \test Call with the last node of a filled list result must be NULL.
 *  \test Call with the any node of a filled list result must right.
 *
 *  \hideinitializer
 */
#define LIST_FIRST( list )  ( LIST_IS_EMPTY( list ) ?  (void*) 0 : ((list)->header.next ) )

/** Retrieve pointer to last element of list.
 *
 *  LIST_LAST() will return the last element of the list. If list is empty NULL will be returned.
 *
 *  \param head      Handle to an existing linked list.
 *
 *  \return          Pointer to the last object in list or
 *                   NULL if list is empty.
 *
 *  \see  LIST_LAST() LIST_NEXT() LIST_PREV() LIST_POP() LIST_UNSHIFT()
 *
 *  \test Call with an empty list result must be NULL.
 *  \test Call with list with only one node - result must be a pointer to the node.
 *  \test Call with filled list - result must be a pointer to the first node.
 *
 *  \hideinitializer
 */
#define LIST_LAST(head)   ( LIST_IS_EMPTY(head) ? (void*) 0 : ((head)->trailer.prev) )

/** Insert a new element before another.
 *
 *  LIST_INSERT() will insert a new node before a given node.
 *  This node can be at an arbitrary position in the list.
 *
 *  \param node         Pointer to an object where the new element
 *                      will be inserted.\n
 *
 *  \param new          Pointer to a new node.
 *
 *  \see LIST_ATTACH()
 *
 *  \test Call with the first node of a filled list.
 *  \test Call with the last node of a filled list.
 *
 *  \hideinitializer
 *
 */
#define LIST_INSERT( node ,new ) do{                              \
                                    (new)->prev=(node)->prev;     \
                                    (new)->next=node;             \
                                    (new)->prev->next=new;        \
                                    (node)->prev=new;             \
                                 }while(0)

/** Insert a new element after another.
 *
 *  LIST_ATTACH() will insert a new node after a given node.
 *  This node can be at an arbitrary position of the list.
 *
 *  \param node         Pointer to an object where the new element should be
 *                      be inserted.
 *
 *  \param new          Pointer to a new node.
 *
 *  \see LIST_INSERT() LIST_UNLINK()
 *
 *  \hideinitializer
 *
 */
#define LIST_ATTACH(node,new) do{                              \
                                 (new)->next=(node)->next;     \
                                 (new)->prev=node;             \
                                 (node)->next=new;             \
                                 (new)->next->prev=new;        \
                              }while(0)

/** *  Add element to the start of a list.
 *
 *  LIST_PUSH_FRONT() will add a new element to the beginning of a
 *  list, right before the first element. For an empty list
 *  this is equivalent to calling LIST_PUSH_BACK().
 *
 *  \param list       Handle to an existing linked list.
 *
 *  \param new        Pointer to an object associated with
 *                    the new list element.
 *
 *  \see LIST_SHIFT()
 *
 *  \hideinitializer
 */
#define LIST_PUSH_FRONT(list,new)   do{                                                   \
                                       (new)->next           = (list)->header.next;       \
                                       (new)->prev           = (void*)&((list)->header);  \
                                       (list)->header.next->prev= new;                    \
                                       (list)->header.next      = new;                    \
                                    }while(0)

/** Add element to the end of a list.
 *
 *  LIST_PUSH_BACK() will add a new element to the end of a list.
 *  If you think of the list as a stack, the function pushes
 *  a new element on top of the stack.
 *
 *  \param list         Pointer to the head of a linked list.
 *
 *  \param new          Pointer to an object associated with
 *                      the new list element.
 *
 *  \see LIST_POP_FRONT()
 *
 *  \hideinitializer
 */
#define LIST_PUSH_BACK(list,new)    do{                                                   \
                                       (new)->prev           = (list)->trailer.prev;      \
                                       (new)->next           = (void*)&((list)->trailer); \
                                       (list)->trailer.prev->next = new;                  \
                                       (list)->trailer.prev       = new;                  \
                                    }while(0)

/**  Remove element from an arbitrary position of a list.
 *
 *  LIST_UNLINK() will remove the passed node from a list. If element is not associated with a
 *  list the behaviour is undefined.
 *
 *  \param node         Pointer to the node which will be unlinked.
 *
 *  \return             Pointer to the object that was associated with
 *                      the element removed from the list. If the list
 *                      is empty, NULL will be returned.
 *
 *  \test Call with the node of a list with only one Element. Result should be pointer to this node.
 *  \test Call with last node of a filled list. Item is removed from list.
 *  \test Call with first node of a filled list. Item is removed from list.
 *  \test Call with any node of a filled list.  Item is removed from list.
 *
 *  \see LIST_UNSHIFT() LIST_POP()
 *
 *  \hideinitializer
 */
#define LIST_UNLINK(node)     do{                                    \
                                    (node)->prev->next=(node)->next; \
                                    (node)->next->prev=(node)->prev; \
                              }while(0)

/** Remove element from the start of a list.
 *
 *  LIST_POP_FRONT() will remove the first element from a list.
 *  If the list contains only a single element, this is
 *  equivalent to calling LNL_POP(). If list is empty, NULL will be returned.
 *
 *  \param list      Handle to an existing linked list.
 *
 *  \param ptr       Pointer to pointer where the object that was associated with
 *                   the element removed from the list is stored. If the list
 *                   is empty, NULL will be returned.
 *
 *  \test Call with an empty list. Result should be NULL.
 *  \test Call with a list with only one node. Result pointer to this node.
 *  \test Call with a filled list. .
 *
 *  \see LIST_POP_BACK() LIST_UNLINK()
 *
 *  \hideinitializer
 */
#define LIST_POP_FRONT(list,ptr) do{                                 \
                                    if( LIST_IS_EMPTY(list))         \
                                    {                                \
                                       *(ptr)=(void*) 0;             \
                                    }                                \
                                    else                             \
                                    {                                \
                                       *(ptr)=(list)->header.next;   \
                                       LIST_UNLINK( *ptr );          \
                                    }                                \
                                 }while(0)

/**  Remove element from the end of a list.
 *
 *  LIST_POP_BACK() will remove the last element from a list.
 *  If you think of the list as a stack, the function pops
 *  an element of the stack.
 *
 *  \param  list     Handle to an existing linked list.
 *  \param  ptr      Pointer to pointer where the object that was associated with
 *                   the element removed from the list is stored. If the list
 *                   is empty, NULL will be stored.
 *
 *  \test Call with an empty list. Result should be NULL.
 *  \test Call with a list with only one node. Result pointer to this node.
 *  \test Call with a filled list. .
 *
 *  \see LIST_POP_FRONT()
 *
 *  \hideinitializer
 */
#define LIST_POP_BACK(list,ptr)  do{                                 \
                                    if( LIST_IS_EMPTY(list))         \
                                    {                                \
                                       *(ptr)=(void*) 0;             \
                                    }                                \
                                    else                             \
                                    {                                \
                                       *(ptr)=(list)->trailer.prev;  \
                                       LIST_UNLINK( *ptr );          \
                                    }                                \
                                 }while(0)

/**  Loop over all list elements.
 *
 *  \code             LIST_FOR_EACH(p,list)
 *                    {
 *                      printf("Datapointer is 0x%x",LIST_DATA(p));
 *                    }
 *  \endcode
 *
 *  \param p         Variable that will receive a pointer
 *                   to the current object.
 *
 *  \param list      Handle to an existing linked list.
 *
 *  \test Call with an empty list. Body will never executed.
 *  \test Call with a list with only one node. Body executed once.
 *  \test Call with a filled list. Body will executed for node in list.
 *
 *  \hideinitializer
 */
#define LIST_FOR_EACH(list,p)  for( (p)=(list)->header.next; (void*)(p) !=(void*)&((list)->trailer); (p)=(p)->next )

/** Test of emptyness.
 *
 * The macro LIST_IS_EMPTY(list) return True if no list element is linked.
 *
 * \param list Pointer to a list object.
 *
 * \return TRUE if list is empty.
 *
 *  \hideinitializer
 */
#define LIST_IS_EMPTY( list )       ((void*)((list)->header.next)==(void*)&(list)->trailer)


/** Number of linked nodes.
 *
 *
 */
 #define LIST_COUNT( list, p, count )  do{                        \
                                          (*(count))=0;                 \
                                          LIST_FOR_EACH( list,*(p) ) \
                                             (*(count))++;              \
                                       }while(0)

/*====================================================================================================================*/

#ifdef __cplusplus
   }
#endif

#endif

/***********************************************************************************************************************
*                             Copyright 2007 Linde Material Handling. All rights reserved.                             *
***********************************************************************************************************************/
